\documentclass[a4paper,10pt]{article}

\usepackage{ifpdf}
\ifpdf
    \usepackage{cmap}
\fi

\usepackage[utf8]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage[russian]{babel}
\usepackage[left=2cm,right=2cm,top=2cm,bottom=2.5cm]{geometry}

\usepackage{amsmath, amssymb}


\begin{document}
\section*{Билет \No 2.24}
{\em Шифрование с открытым ключом. Алгоритмы RSA и Эль-Гамаля.
Методы распределение ключей. Алгоритмы разделения секрета.}

\section{Шифрование с открытым ключом} 
{\bf Криптографическая система с открытым ключом} (или {\bf Асимметричное шифрование, Асимметричный шифр})~--- система шифрования 
в которой открытый ключ передаётся по незащищённому каналу, и
используется только для шифрования сообщения. Для расшифровывания сообщения используется секретный ключ.

Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах
{\it TLS\/} и его предшественнике {\it SSL} (лежащих в основе {\it HTTPS}), а так же {\it SSH}, {\it PGP}, {\it S/MIME} и т.\,д.

Рассмотрим случай, когда отправитель хочет послать получателю секретное сообщение.
\begin{enumerate}
   \item Получатель генерирует 2 ключа. Один их них открытый, другой закрытый (секретный). При этом закрытый ключ не должен передаваться по
      открытому каналу.

   \item Отправитель с помощью открытого ключа шифрует сообщение.
 
   \item Получатель с помощью закрытого ключа дешифрует сообщение.

\end{enumerate}

\subsection{Преимущества}
Преимущество асимметричных шифров перед симметричными шифрами состоит в отсутствии необходимости предварительной передачи секретного ключа
по надёжному каналу. Сторона, желающая принимать зашифрованные тексты, в соответствии с используемым алгоритмом вырабатывает пару «открытый
ключ~--- закрытый ключ». Значения ключей связаны между собой, однако вычисление закрытого ключа по открытому должно быть невозможным с
практической точки зрения. Открытый ключ публикуется в открытых справочниках и используется для шифрования информации контрагентоми.
Закрытый ключ держится в секрете и используется для расшифровывания сообщения, переданного владельцу пары ключей.
Для удостоверения аутентичности самих публичных ключей, передаваемых по открытому каналу или получаемых из справочника, обычно
используют сертификаты.

\subsection{Недостатки} 
Асимметричные криптосистемы в чистом виде требуют существенных вычислительных ресурсов, потому на практике используются в сочетании с
другими алгоритмами. Обычно сообщение шифруют временным (сессионным) симметричным ключом, а сам симметричный ключ шифруют асимметричным.

\subsection{Электронная цифровая подпись}
Для ЭЦП сообщение предварительно подвергается хешированию, а с помощью асимметричного ключа подписывается лишь относительно небольшой
результат хеш-функции.

\section{Алгоритмы RSA и Эль-Гамаля}
\subsection{RSA}
Описание {\bf RSA} было опубликовано в 1977 году {\it Рональдом Райвестом (Ronald Linn Rivest), Ади Шамиром
(Adi Shamir)} и {\it Леонардом Адлеманом (Leonard Adleman)} из MIT.

\paragraph{Принцип работы шифросистемы.} 
Для того, чтобы сгенерировать пару ключей выполняются следующие действия:
\begin{enumerate}
    \item Выбираются два больших случайных простых числа $p$ и $q$.
    \item Вычисляется их произведение $n=pq$.
    \item Вычисляется Функция Эйлера $\varphi(n)=(p-1)(q-1).$ 
        ({\bf Функция Эйлера} $\varphi(n)$, где $n$~--- натуральное число, равна количеству натуральных чисел, не больших
        $n$ и взаимно простых с ним.)
    \item Выбирается целое $e$ такое, что $1<e<\varphi(n)$ и $e$ взаимно простое с $\varphi(n)$.
    \item С помощью расширенного алгоритма Евклида находится число $d$ такое, что 
        $ed\equiv 1\pmod{\varphi(n)}$. Это значит, что $de = 1 + k\varphi(n)$ при некотором целом $k$.
\end{enumerate}

Число $n$ называется модулем, а числа $e$ и $d$~--- открытой и секретной экспонентами, соответственно.
Пара чисел $(n,e)$ является открытой частью ключа, а $d$~--- секретной. Числа $p$ и $q$ после
генерации пары ключей могут быть уничтожены, но ни в коем случае не должны быть раскрыты.
 
\paragraph{Шифрование.}
Для того, чтобы зашифровать сообщение $m<n$ вычисляется $c=m^e\bmod n. $
Число $c$ и используется в качестве шифротекста. 

\paragraph{Дешифрование.}
Для расшифровывания нужно вычислить $m=c^d\bmod n.$
Нетрудно убедиться, что при расшифровывании мы восстановим исходное сообщение:
    $$c^d\equiv (m^e)^d\equiv m^{ed}\pmod n.$$
Из условия $ed\equiv 1\pmod{\varphi(n)}$
следует, что $ed=k\varphi(n)+1$ для некоторого целого $k$, следовательно
    $$m^{ed}\equiv m^{k\varphi(n)+1}\pmod n.$$
Согласно теореме Эйлера
    $m^{\varphi(n)}\equiv 1\pmod n, $
поэтому
$$m^{k\varphi(n)+1}\equiv m \pmod n \quad \Rightarrow \quad c^d\equiv m\pmod n.$$

\paragraph{Криптостойкость.} 
Безопасность RSA основана на трудности задачи разложения на множители.

\paragraph{Цифровая подпись.}
RSA может использоваться не только для шифрования, но и для цифровой подписи. 
Подпись $s$ сообщения $m$ вычисляется с использованием секретного ключа по формуле:
    $s=m^d\bmod n.$
Для проверки правильности подписи нужно убедиться, что выполняется равенство
    $m=s^e\bmod n.$

\subsection{Elgamal}
Шифросистема {\bf Эль-Гамаля} {\it (Elgamal)}~--- была предложена в 1984 году. 
В частности стандарты электронной цифровой подписи в США и России базируются именно на ней.
\paragraph{Принцип работы шифросистемы.} 
\begin{enumerate}
   \item Генерируется случайное простое число $p$.
   \item Выбираются случайные числа $x$ и $g$ так, что $1 < x < p$, $1 < g < p$.
   \item Вычисляется $y = g^x \mod p$.
\end{enumerate}

Открытым ключом является тройка $(p,g,y)$, закрытым ключом~---  число $x$.

\paragraph{Шифрование.}
Будем обозначать исходное сообщение $M$.

\begin{enumerate}
   \item Выбирается случайное секретное число $k$, взаимно простое с $p - 1$.
   \item Вычисляется $a = g^k\bmod p$, $b = y^kM\bmod p$, где $M$~--- исходное сообщение.
\end{enumerate}

Пара чисел $(a,b)$ является шифротекстом. При этом длина шифротекста больше длины исходного сообщения $M$ вдвое.

\paragraph{Дешифрование.} 
Зная закрытый ключ $x$, исходное сообщение получается из шифротекста $(a,b)$ по формуле: $M = b / a^x\bmod p.$

Нетрудно проверить, что
$$a^x\equiv g^{kx}\pmod{p}\quad\text{и}\quad\frac{b}{a^x}\equiv \frac{y^kM}{a^x}\equiv \frac{g^{xk}M}{g^{xk}}\equiv M \pmod{p}.$$

\paragraph{Криптостойкость.} 
Криптостойкость данной схемы основана на сложности проблемы дискретного логарифмирования (по известным $p$, $g$ и $y$ приходится искать показатель
степени $x$: $y \equiv g^x \pmod{p}.$


\section{Методы распределение ключей}
{\bf Протокол распределения ключей} {\it ([secret] key distribution [agreement, sharing, exchange, generation]
protocol)}~--- это протокол, который позволяет его участникам выработать общую секретную информацию
(общий секретный ключ), обмениваясь сообщениями по открытым для прослушивания каналам. 
В протоколе может предполагаться наличие некоторого дополнительного
участника, пользующегося абсолютным доверием всех остальных участников, которого мы будем называть
центром доверия. Подчеркнем, что перед началом выполнения протокола не предполагается наличие у
участников какой-либо общей секретной информации. В процессе выполнения протокола участники
обмениваются сообщениями по открытым каналам связи, после чего каждый участник вычисляет свой
элемент некоторого множества $K$, называемого пространством ключей. Если все участники вычислили
один и тот же элемент из $K$, то этот элемент и является общим секретным ключом. 

Задача противника состоит в вычислении общего секретного ключа. Для этого он может как просто
подслушивать сообщения участников друг другу {\it (пассивный противник (passive adversary,
eavesdropper))}, так и вмешаться в выполнение протокола путем замены сообщений участников своими
сообщениями, выдавая себя за одного из законных участников {\it (активный противник (active adversary,
impersonator))}. 

\subsection{Алгоритм Диффи-Хелмана}
Эта схема используется в {\it SSL}. Рассмотрим взаимодействие двух участников~--- Алисы и Боба.
\begin{enumerate}
    \item Алиса и Боб выбирают конечную циклическую группу $G$ и элемент $g\in G$.
        (Это обычно происходит заранее: $G$ и $g$ являются публичными данными, т.\,е. известными
        всем противникам.) 
    \item Алиса выбирает случайное число $a$ и посылает Бобу  $g^a$.
    \item Боб   выбирает случайное число $b$ и посылает Алисе $g^b$.
    \item Алиса вычисляет $K = (g^b)^a$.
    \item Боб   вычисляет $K = (g^a)^b$.
\end{enumerate}
Боб и Алиса оба обладают элементом $g^{ab}$ группы $G$, который они могут использовать как секретный
ключ. Перед противниками стоит задача зная $G$, $g$, $g^a$ и $g^b$ определить  $g^{ab}$.
Считается, что эта задача {\it (проблема Диффи-Хелмана)} сложна.

\section{Алгоритмы разделения секрета}
С помощью алгоритмов разделения секрета можно разбить информацию на доли таким образом, что пока у
вас не будет необходимого количества долей, вы не будете иметь никакого представления об этой
информации, но если вы соберете нужное количество долей, то сможете ее восстановить.

Более формально, в схеме разделения секрета выделяется {\it дилер (dealer)} и $n$ игроков.
Дилер распределяет секрет между игроками таким образом, чтобы любая группа из $t$
игроков ($t$ называется {\it порогом}) могла восстановить секрет, но никакая группа из меньшего
количества игроков не могла бы этого сделать. Такая система называется $(t,n)$ пороговой схемой.


Для примера, представим, что дилер разделил секретное слово ``\texttt{password}'' 
на 4 части ``\texttt{pa-{-}-{-}-{-}},'' ``\texttt{-{-}ss-{-}-{-}},'' ``\texttt{-{-}-{-}wo-{-}},'' и
``\texttt{-{-}-{-}-{-}rd}'', и раздал 4 игрокам.
Даже если соберется группа из 3 игроков, им придется гадать над значением неизвестных двух букв.

\subsection{Тривиальные схемы}
Пусть $t = n$. 
Рассмотрим следующие схемы.

\begin{enumerate}
    \item Секрет~--- секретное число $s$.
        Дилер посылает каждому игроку $i\neq n$ случайное число $r_i$, а игроку с номером $n$
        число $$s - r_1 - r_2 - \cdots - r_{n - 1}.$$
        Секрет равен сумме чисел, которые есть у игроков.

    \item Секрет~--- число $s$ с фиксированным числом битов.
        Дилер посылает каждому игроку $i\neq n$ случайное число $b_i$, а игроку
        с номером $n$ $$s\oplus b_1\oplus b_2 \oplus\cdots \oplus b_{n-1}.$$
        Секрет равен XOR-у всех чисел, которые дилер послал игрокам.
\end{enumerate}

\subsection{Пороговая схема Шамира}
Основная идея пороговой схемы Шамира заключается в том, что 2 точки задают прямую,
3 точки~--- параболу, 4 точки~--- кубическую кривую и т.\,д.
Таким образом, нужна $n+1$ точка, чтобы определить полином степени $n$.

Предположим, необходимо построить $(t,n)$ пороговую схему для разделения секрета $s$ (НУО, будем
считать $s$ числом).

\begin{enumerate}
    \item Дилер выбирает $t-1$ коэффициент $a_1,\ldots, a_{k-1}$ и полагает $a_0 = s$.
    \item Определяет функцию $f(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots+a_{k-1}x^{k-1}$.
    \item Посылает каждому игроку $i$ пару $(i, f(i))$.
\end{enumerate}
Таким образом, любая группа из $k$ игроков располагает $k$ точками, 
а значит может восстановить $f$ по этим точкам и определить $a_0$, т.\,е. секрет $s$.

\subsection{Схема Блекли}
Две не параллельные прямые пересекаются в одной точке, три не параллельные плоскости также
пересекаются в одной плоскости. В общем случае $n$ $n$-размерных гиперплоскостей (из $\mathbb{R}^n$)
пересекаются в одной точке.

Аналогично предыдущей схеме, построим $(t,n)$ пороговую схему для разделения секрета $s$ (НУО, будем
считать $s$ числом).

\begin{enumerate}
    \item Дилер кодирует секрет в одной из координат некоторой точки в пространстве $\mathbb{R}^t$.
        (Если дилер закодирует сразу во всех координатах, то какой-нибудь противник сможет
        располагая набором из менее чем $t$ ``кусочков'' сможет получить дополнительную информацию о
        секрете, т.\,к. он знает, что точка лежит на его плоскости.)
    \item Дилер генерирует $n$ непараллельных $t$-размерных гиперплоскостей, пересекающихся в точке
        с секретом, и посылает по одной каждому игроку.
\end{enumerate}
Секрет в группе из $t$ игроков восстанавливается посредством вычисления точки пересечения $t$
гиперплоскостей.

\paragraph{Замечание.} Схема Блекли менее эффективна по размеру посылаемых сообщений по сравнению со схемой Шамира.
Это можно исправить введя ограничения на плоскости. Получившаяся схема будет эквивалентна
схеме Шамира.

\end{document}
